Discussion:Argument de la diagonale de Cantor

àmha il faudrait changer la conclusion car le "a fortiori" est abusif : en effet il existe une bijection de [0 1] dans $\mathbb {R}$ ex: x->Argth(2x-1) L'indénombrabilité de [0 1] équivaut donc à celle de $\mathbb {R}$ contrairement à ce que semble indiquer le "a fortiori"

[0, 1] est un sous-ensemble de $\mathbb {R}$, je ne vois pas ou est le problème de dire que si [0, 1] n'est pas dénombrable à fortiori R ne l'est pas non plus (mais je considére à fortiori comme "à plus forte raisons ou égales"), sinon on peut remplacer par « l'intervalle [0, 1] n'est pas infini dénombrable donc $\mathbb {R}$ ne l'est pas » phe 23 déc 2004 à 19:25 (CET)

Pourquoi ne pas parler de cardinalité au lieu de dire "P(S) est plus grand que S" ?

Bon article. J'ai unifié non-dénombrabilité, non dénombrabilité et indénombrabilité en non-dénombrabilité, etc. A mon avis l'article serait meilleur sans démarrer d'emblée par un raisonnement par l'absurde : ce qui est montré c'est, étant donné(e) une suites de réels, comment construire (je dis bien construire) un nombre réel qui n'est pas dans la suite. D'autre part, en plus du théorème de (l')arrêt, on pourra ajouter quelques mots menant a Classification de Baire car l'argument diagonal est aussi utilisé pour démontrer qu'il y a aleph₀ classes distinctes de Baire, et de même pour les classes de boréliens (cf Tribu borélienne). CD 19 jan 2005 à 21:44 (CET)

Changements faits, sauf allusion à "Classe de Baire". CD 3 fev 2005 à 21:21 (CET)

L'argument diagonal semble dû à Du Bois Reymond, qui l'a utilisé le premier en analyse. Source, Smorynski "Logical Number theory", puis google, pas trouvé de source directe.

J'ai l'habitude de dire et d'entendre argument diagonal et pas argument de la diagonale : quel est l'usage le plus courant ?

• "argument diagonal" indiscutablement. (Mais les deux titres sont justes)  <STyx @ 23 mai 2006 à 15:38 (CEST)

On devrait indiquer ce que montre la version "plus compréhensible" (pas de surjection de N dans P(N)). Proz 25 avril 2006 à 21:18 (CEST)

caractère constructif

Réaction à la modification d'Ektoplastor (9 juillet 2007 17:57) : si on veut conserver l'aspect constructif du raisonnement pour les réels, il ne faut pas supposer que leur développement (décimal ou autre base) est propre : en entrée ça ne sert à rien, c'est seulement en sortie qu'il faut faire attention. Le réel diagonal dépend du développement "choisi" (en fait, dans un contexte calculatoire, celui que le calcul donne) ce qui peut surprendre mais n'est pas gênant. Plus généralement j'adhère à l'avis de CD ci-dessus, qui avait rédigé l'argument. On peut, comme il l'avait fait (j'avais ajouté la précision), passer la chose sous silence.

Par ailleurs les paragraphes sur le théorème de Cantor et la calculabilité ne sont plus en cohérence avec le début, faux même pour ce dernier à cause de ce qui précède (pour le reste je suis d'accord évidemment avec les indications historiques, et n'ai rien contre une exposition préliminaire sur les suites, cas plus simple, encore que les réels sont peut-être plus familiers). Proz 9 juillet 2007 à 19:25 (CEST)

L'article est devenu d'une part partiellement faux, d'autre part incohérent puisque les paragraphes que j'avais ajouté s'appuyaient sur la version antérieure. Après réflexion la version précédente me semble plus intéressante, et celle actuelle s'en déduit facilement. Je préfère donc revenir à une version antérieure également à mes interventions pour l'exposé de l'argument diagonal, qui avait l'avantage de la simplicité et de l'élégance. Je mettrai ce que j'avais ajouté en commentaires dans un paragraphe à part, de même que les considérations sur les suites. Proz 23 juillet 2007 à 21:28 (CEST)

Hormis les erreurs de notation, où vois-tu une erreur dans ma version (hormis les erreurs de notation) ?

Tout d'abord, je trouve que démontrer directement que l'ensemble R est non dénombrable est troublant. Pourquoi ? Parce que au final, on démontre ni plus ni moins que l'ensemble des suites de 0, 1, ..., 9 est non dénombrable ! Démontrer ce simple résultat est plus simple. Et si de plus, il est confirmé que Cantor s'est intéressé aux suites avec deux éléments, cela fournirait un argument de plus en ma faveur (approche historique, qu'il faudrait, dans la mesure du possible, privilégier).

Cohérence : dans la version actuelle ([1]), je ne vois vraiment aucune cohérence entre la partie 1 et la partie 2. Donc à toi de me l'expliquer ! (Excuse-moi si elle ne me parait pas clairement exposée, mais sincèrement, je ne la vois pas.)

Voilà comment moi je vois les choses : les parties de N se codent par des suites de 0 et de 1 (appartenance ou non de l'entier n dans l'ensemble considéré). Etant donné une suite A_n de parties de N, on lui associe la suite $(u_{n})$ de suites de 0 et de 1. On construit une suite w par la méthode exposée dans le premier paragraphe, et on lui adjoint la partie correspondante B de N. L'entier n appartient à B ssi il n'appartient pas à A_n : B est exactement l'ensemble des entiers n qui n'appartiennent pas à A_n. La construction dans le paragraphe 1 qui aurait donné pour les suites de 0 et de 1 se généralise pour les parties d'un ensemble infini S quelconque.

Dans ta présentation, il y a deux arguments de la diagonale qui me semblent présentés comme totalement différents ; ce qui n'est pas le cas dans la présentation que je souhaite proposer. Ekto - Plastor 24 juillet 2007 à 13:49 (CEST)

Si on y voit deux arguments différents de la diagonale ce n'est pas ce que j'ai souhaité. J'ai bien écrit que le raisonnement était le même pour les suites que pour les réels en plus simple, et que pour l'ensemble des parties de N, c'était identique aux suites de deux éléments. Sinon, j'avais cru expliquer le problème au dessus. J'essaye d'être plus clair. Je me sers explicitement dans le paragraphe sur la calculabilité de la présentation (qui elle n'est pas de moi, elle date essentiellement de 2005) pour dire que le raisonnement est constructif y compris pour les réels, (pas de problème pour les suites), et accessoirement que le réel diagonal est dans ]0,1[, d'où l'incohérence. Pour mettre les développements des décimaux sous forme propre, il faut savoir que ce sont des décimaux. Etant donné un réel calculable (disons que l'on peut engendrer le développement décimal aussi loin que l'on veut par un procédé mécanique), on ne peut pas nécessairement décider que c'est un décimal (théorème de Rice) et donc choisir le développement propre. Ton raisonnement qui choisit au départ le développement dit propre n'est donc plus constructif (le raisonnement que tu avais effacé l'était, et ce n'est pas par hasard, vu les commentaires de 2005 que tu as dans la page de discussion), donc le paragraphe sur la calculabilité devenait en partie faux (bien entendu cela reste correct pour ce que tu écris qui ne concerne que la non dénombrabilité). Par ailleurs je trouve la présentation antérieure élégante et concise mais finalement assez riche puisqu'elle traite de façon optimale les réels. Bien qu'il soit exact que sur le fond, et que je sois tout à fait au courant (et la personne qui l'avait rédigé très certainement également), qu'il s'agit d'un raisonnement sur les suites de chiffres, l'exposé fait d'abord comme si c'était le cas (j'avais fait l'erreur de vouloir tout de suite expliciter, mais j'ai déplacé ce que j'avais ajouté), donc n'est pas plus compliqué. D'autre part les développements décimaux me semblent plus familiers que les suites, et l'ensemble des réels que l'ensemble des parties de N, où l'ensemble des suites de 0 et de 1. Je trouve dommage de l'abandonner pour ta version, qui, comme tu le remarques toi-même, est finalement identique au raisonnement « imagé » dans le paragraphe qui suit. Il est bien exact que Cantor le rédige pour des suites de deux caractères, mais je ne suis pas pour privilégier en toute chose l'approche historique (la mentionner oui). Ces dernières objections ne sont pas de fond, il est toujours envisageable de présenter les choses autrement, mais pas en rendant l'article incohérent. Proz 24 juillet 2007 à 15:39 (CEST)

Je n'avais pas retouché le paragraphe Calculabilité. Si une erreur s'était introduite dans ce paragraphe, elle n'est certainement pas de moi.

Je trouve que la partie 1 juxtaposée à la partie 2 manque de cohérence, mais c'est certainement un avis personnel. Je pourrais proposer en septembre une autre version (sur une de mes sous-pages).

Le développement décimal d'un entier n'est pas quelque chose d'évident en soi car il repose sur la notion de limite en analyse. En particulier, lorsqu'on écrit 2,76etc, le etc n'a rien d'évident (calculabilité mise à part). La notion de suites est plus facilement accessible.

Je ne vois pas pourquoi on serait obligé de rédiger la partie 1 en vue de la partie 3. Tu peux au contraire retravailler la partie 3 en vue d'une éventuelle réécriture de la partie 1 (ce qui me semble plus logique). Tout cela dépend de choix rédactionnels.

Tu pourrais aussi ouvrir en remarquant que les suites standards appartiennent à un sous-ensemble fini. Dans l'IST, l'infini provient de l'existance d'elements non standards. On peut donc remarquer que, "en général", la suite obtenue sera non standard. On pourrait insérer des mises en garde sur les transferts illégaux par exemple. Enfin, il faudrait réfléchir sur la structure de l'article et la meilleure présentation possible des idées. Ma modification dont tu faisais référence n'avait pour principale motivation que d'améliorer la mise en page, souvent négligée dans les articles de Wikipédia. Ekto - Plastor 24 juillet 2007 à 16:20 (CEST)

J'ai bien vu que tu n'as pas retouché, ni à mon avis lu le § sur la calculabilité. Mais comme il fait référence au raisonnement du début, tu peux concevoir qu'en modifiant celui-ci il devienne faux par ricochet. Je suis bien-sûr d'accord sur le fait que la notion de suite est la plus primitive. On n'est pas obligé de rédiger une partie en vue d'une autre, mais quand c'est fait on ne pas modifier une partie sans en tenir compte. Pour ce qui est du raisonnement diagonal dans le cadre de l'analyse non standard ça me dépasse. Il ne faudrait sûrement pas en faire l'approche par défaut, mais s'il y a des choses intéressantes à dire sur le sujet qui concernent bien l'argument diagonal ... Il y a sinon d'autres choses à dire (par ex. hiérarchies de fonction de du Bois Reymond, voir aussi l'avis de l' Utilisateur:CD ci-dessus). Proz 24 juillet 2007 à 17:11 (CEST)

Une approche troublante sur la cardinalité de R

Bonjour, je viens exposer ici une manière de voir à propos de la cardinalité de R. Avant de lire le problème avec la problématique de la diagonale de cantor, j'avais tendance à penser que la cardinalité de R était la même que celle de N, évidement au final je n'ai pas raison, mais c'est une manière de voir très troublante, voici le principe: tout nombre R peut s'écrire par une phrase contenant des caractères d'imprimerie, par exemple la phrase :

"racine de 2"

D'autre part on peut créer une bijection de N dans l'ensemble des phrases possibles, par exemple en supposant qu'il y ait 50 types de caractères d'imprimerie possible dans ces phrases ( Les 26 lettres de l'alphabet, les 10 chiffres, le caractères "espace" et quelques autres signes). On crée cette bijection ainsi:On transforme le nombre compris dans N en un nombre en base 50, et on transforme chaque chiffre de ce nombre en base 50 en un caractère de la phrase correspondant à ce nombre compris dans N:

• pour 1 on obtient la phrase : "a"
• pour 2 on obtient la phrase : "b"
• pour 53 soit 1 * 50 + 3 * 1 on obtient : "ac"
• et ainsi de suite...

On a donc ici une bijection de N vers toutes les phrases possibles.On comprend bien que certains phrases telles que "a", "b" ou "ac" ne veulent rien dire, on les supprime donc, gardant: "1" , "2" , "Racine de 2" etc....Et voila donc toute la bizarrerie du problème: étant donné que tout nombre R peut s'écrire par une phrase valide, et que il existe une bijection de N dans ces phrases valides, il y a donc une bijection entre N et R, donc N aurait la même cardinalité que R.

Ça parait tout à fait logique, sauf que mon approche ne tient pas la route face à la problématique apportée par la diagonale de cantor ... mais ça reste très troublant tout de même!

Qu'en pensez vous? Merci

--Nicobzz (d) 28 février 2010 à 18:12 (CET)

L'ensemble des phrases (suites finies de caractères d'un alphabet, lui-même fini) est effectivement dénombrable. Donc l'ensemble des réels qu'on peut décrire par une phrase (par exemple: « racine de deux ») est dénombrable. Comme l'ensemble R est de cardinal strictement supérieur au cardinal de l'ensemble N, cela prouve simplement que « la plupart » des nombres réels ne peuvent être décrits par une « phrase » (l'erreur est dans l'affirmation : « tout nombre réel peut s'écrire par une phrase contenant des caractères d'imprimerie » ; en fait, les réels que l'on peut ainsi décrire, bien qu'en nombre infini, ne constituent qu'une petite partie de R). Vivarés (d) 28 février 2010 à 18:52 (CET)

L'ensemble des réels déscriptibles par une phrase est même de mesure nulle dans R (bien qu'infini..). --Jean-Christophe BENOIST (d) 28 février 2010 à 19:32 (CET)

La dénombrabilité est une propriété plus forte que la négligeabilité: tout sous-ensemble dénombrable de R est de mesure (de Lebesgue) nulle. Vivarés (d) 28 février 2010 à 19:42 (CET)

Merci pour vos réponses, en fait ce qui me parait vraiment étrange c'est cela: dans l'ensemble que j'ai défini comme étant une bijection (en me remémorant mes souvenirs de terminal, plutôt une surjection) de N dans l'ensemble de tous les nombres de R que l'on peut écrire par une phrase, on peut malgré cela trouver un autre nombre compris dans R qui peut s'écrire par une phrase, celui ci étant: "Le nombre de la diagonale de Cantor de la surjection que j'ai précédemment défini". Hors si on essaye de rajouter ce nombre à ma surjection soit on met tel quel:"Le nombre de la diagonale de Cantor de la surjection que j'ai précédemment défini" et là finalement ce nombre n'est pas définissable, soit on le met ainsi:"Le nombre de la diagonale de Cantor de la surjection que j'ai précédemment défini(en sautant ce nombre que je viens de définir)", mais de toutes manières on pourra créer un nombre de la diagonale de Cantor de cette nouvelle suite qui malgré qu'il soit définissable dans une phrase, ne sera pas défini dans ma suite!

Donc ce qui me parait étrange c'est que malgré qu'apparemment ma suite contient tous les nombre R rédigeable, on peut toujours en trouver un autre également rédigeable, non?

Voir paradoxe de Richard (indiqué au début de l'article, qui est loin d'être parfait, mais on peut quand même y trouver des choses). Proz (d) 3 mars 2010 à 20:43 (CET)

Ah merci! apparemment c'est correspond à la même idée!

N et R sont effectivement équipotents, tout au moins si l'on adopte une conception "potentielle" de l'infini, et non "actuelle", comme c'est le cas depuis Cantor. Avec sa diagonale, Cantor démontre seulement qu'on ne peut jamais dénombrer ALEPH, dans tous les sens. En inférer qu'il y a plus de réels infinis que de réels finis est une pure extrapolation dûe à notre conception de l'infini (actuel). 90.39.92.16 (d) 20 juin 2010 à 16:05 (CEST)

Si on parle de N où de R on est dans l'infini en acte et non potentiel et dans ce cas ces 2 ensembles ne sont pas équipotents. --Epsilon0 ε₀ 20 juin 2010 à 21:07 (CEST)

Rien n'oblige à considérer N comme un tout surdimensionné (= Aleph), seulement notre conception de l'infini. Dans N, je peux dénombrer "autant d'éléments que je veux", jamais une infinité. C'est ce "autant d'éléments que l'on veut" qui est un tout, pas ALEPH. "Autant d'éléments que l'on veut" est à la fois une partie et un tout. L'infini ne se comporte pas comme le fini, c'est un processus ouvert. 90.56.217.141 (d) 21 juin 2010 à 09:01 (CEST)

Je dirais plutôt que "infini" est un adjectif, qui est susceptible de s'appliquer à des choses, et "ouvert" est un adjectif, qui est susceptible de s'appliquer à des processus. Ça fait longtemps que je me dis que je vais m'attaquer à l'article Constructivisme (mathématiques) mais ça n'a pas l'air simple du tout, les sources me semblent pas très d'accord entre elles. Si le coeur vous en dit .... Michel421 _{parfaitement agnostique} 7 août 2010 à 09:45 (CEST)

Difficulté sur la conclusion ...

L'argument diagonal construit un nombre qui n'est pas présent dans l'énumération initiale... Il est "en plus"... donc l'ensembre qui le contient est "plus' grand que l'ensemble des entiers. L'objection mathématique vient de la théorie de Cantor des cardinaux... Cependant il me semble qu'une précision plus utile viendrait de la réponse à cette objection : dans la démonstration de Card(Q) = Card(N), on construit une énumération des fractions a/b par 2^a . 3^b . Il suit que 2^a . 3^b . 5 est un entier qui n'est pas dans l'énumération... donc Card(N) serait plus grand que Card(Q) ? Evidemment Non ! La conclusion est que Card(N) est au moins aussi grand que Card(Q)... Galilée se méfiait déjà de ces pièges faciles... Si vous pouviez clarifier l'article sur ce point... Cordialement, Xavou 14 octobre 2011

Je n'ai pas vu où, dans l'article, il y avait la démonstration Card(Q) = Card(N), avec une énum des fractions a/b par 2^a . 3^b. D'où prenez-vous cet exemple ? Normalement, on construit une injection de Q => N pour démontrer que Card(Q) = Card(N) (l'injection de N=>Q étant triviale, la bijection s'ensuit, théorème de Cantor-Bernstein). Si 2^a . 3^b est la construction d'une injection, il est normal que des entiers ne soient pas dans la liste.. --Jean-Christophe BENOIST (d) 14 octobre 2011 à 23:54 (CEST)

+1 J-C B. Prendre l'injection Q --> N avec a/b --> 2^a * 3^b prouve en effet que que Card(N) est au moins aussi grand que Card(Q), la réciproque étant immédiate (l'identité). On retombe sur nos pieds avec le thm de Cantor-Schröder-Bernstein : si il existe une injection de A dans B et une injection de B dans A alors il existe une bijection entre A et B. A noter que ce thm est immédiat si on a l'axiome du choix mais se démontre aussi sans (donc par construction explicite de la bijection étant données les 2 injections ; même si en général ce n'est pas très simple). Et pour revenir à ce présent article vous pouvez essayer (exercice intéressant) mais vous ne trouverez pas d'injection de R dans N car justement cet argument de la diagonale prouve qu'il n'y en a pas. Rien, me semble t-il, qui pourrait gêner l'esprit perspicace d'un Galilée lisant cet article et se réveillant quelques siècles après mise en tombe ; il peut dormir en paix ;-). Maintenant Xavou, si un aspect de l'article vous semble à clarifier, dites précisément quoi (quelle phrase) et on tentera de mieux l'expliciter. Cordialement --Epsilon0 ε₀ 15 octobre 2011 à 02:04 (CEST)

Je pense que le problème vient de "Pour démontrer que \mathbb{R} est non dénombrable, il suffit de démontrer la non dénombrabilité du sous-ensemble [0,1] de \mathbb{R}, donc de construire, pour toute partie dénombrable D de [0,1], un élément de [0,1] n'appartenant pas à D."

Dans cette phrase le pour toute est fondamental et signifie que [0;1] n'est égal (à une bijection près) à aucune partie dénombrable de [0;1], donc est non dénombrable. Effectivement, si on lit trop vite en oubliant le pour toute, on tombe dans le raisonnement pointé par xavoux. ---- El Caro ^bla 15 octobre 2011 à 13:10 (CEST)

preuve fausse ?

Une question surement très simple pour les experts mais pas simple à poser, je me lance : Si la diagonale complémentaire est effectivement différente de toutes les valeurs de la suite énumérative, c'est justement parce que cette suite comporte n nombres de chacun n décimales. Or si cette suite comportait 2^n nombres de n décimales, il serait alors impossible de construire une diagonale différente, puisque avec n décimales, il existe au plus 2^n combinaisons de chiffres. Et ainsi la diagonal de Cantor ne prouverait pas (par contradiction) la non dénombrabilité de R.

Euh, non: la suite n’a pas n nombres de n décimales , mais une infinité dénombrable de nombres ayant une infinité de décimales. Du coup, votre raisonnement semble peu compréhensible (et dans tous les cas, si vous pensez pouvoir réfuter Cantor, vous vous exposez à d’étranges déconvenues).—Dfeldmann (discuter) 13 octobre 2019 à 19:16 (CEST)

Peut-être que par n vous voulez parler de la taille de l’ensemble des entiers, qui se note aleph_0. Alors si vous voulez dire qu’il existe une bijection entre 2^aleph_0 (qui est la taille de l’ensemble des parties de N) et [0, 1] sur R, alors oui c’est juste. Mais cela prouve justement que R n’est pas dénombrable car aucun ensemble n’est bijectable avec l’ensemble de ses parties. --Epsilon0 ε₀ 13 octobre 2019 à 21:27 (CEST)

[0,1] ou [0,1[

Une IP a modifié le 18 novembre 2015 l'intervalle dont il est démontré qu'il n'est pas dénombrable avec un argument faux (elle ignorait que 1 = 0,9999...). Ca n'a pas grande importance, donc pas sûr que ça vaille la peine de revenir en arrière. La seule chose c'est de rester cohérent et ne pas mélanger les deux comme dans la modification que je viens d'annuler. Proz (discuter) 10 septembre 2020 à 12:08 (CEST)